The present invention relates to a cache system and a cache processing method to be applied to a data processing unit such as an MPU (MicroProcessor Unit), a CPU (Central Processing Unit), etc. for reducing access time to external memory such as main memory, and in particular, to a cache system and a cache processing method in which full-set associative cash memory capable of preserving cache lines of high usage frequencies is coupled with non-full-set associative cash memory (direct mapping cache memory, 2-way set associative cache memory, 4-way set associative cache memory, 8-way set associative cache memory, etc.) and thereby the cache hit rate is increased.
Cache or cache memory is widely used for reducing access time of an MPU, a CPU, etc. of high data processing speed to memory of low data processing speed such as main memory. Especially, hierarchical cache memory composed of a primary cache memory and a secondary cache memory is widely used in order to increase program execution speed of the MPU, CPU, etc. and thereby improve throughput of systems including the MPU, CPU, etc. Generally, cache memory is provided with a cache table for storing a plurality of tags and data corresponding to the tags. A tag extracted from input address data is compared with tags which have been stored in the cache table, and if the extracted tag matched one of the stored tags, data corresponding to the matched tag is selected out and outputted from the cache table to the MPU, CPU, etc. Thereby, the number of access to external memory (such as main memory of low data processing speed) is reduced, and thereby high speed data processing of the MPU, CPU, etc. is realized.
As the cache memory, full-set associative cash memory and direct mapping cache memory are well known. The direct mapping cache memory can implement high speed access with a small circuit scale, however, its cache hit rate is easily deteriorated. On the other hand, the full-set associative cash memory requires more complicated circuit composition and larger power consumption, however, preservation of high-hit-rate cache lines is possible in the full-set associative cash memory. Incidentally, 2-way set associative cache memory, 4-way set associative cache memory and 8-way set associative cache memory are also well known as non-full-set associative cache memories having similar functions to the direct mapping cache memory.
FIG. 1 is a schematic block diagram showing typical conventional direct mapping cache memory. The direct mapping cache memory shown in FIG. 1 includes a cache table 801 for storing a plurality of tags and data corresponding to the tags, a comparator 802, an AND gate 803 and a data selector 804. Each cache line of the cache table 801 is also provided with a xe2x80x9cvalid bitxe2x80x9d for indicating whether the cache line is valid or invalid. A valid bit xe2x80x9c1xe2x80x9d indicates that the cache line is valid, and a valid bit xe2x80x9c0xe2x80x9d indicates that the cache line is invalid. At the top of FIG. 1, an example of an input address data xe2x80x9c00000040xe2x80x9d (hex) is shown. The input address data includes a tag, an index and an offset. In the case of the input address data xe2x80x9c00000040xe2x80x9d, the tag is xe2x80x9c00000xe2x80x9d (the front 5 hexadecimal digits of the input address data, for example), the index is xe2x80x9c04xe2x80x9d (the next 2 hexadecimal digits of the input address data, for example), and the offset is xe2x80x9c0xe2x80x9d (the last 1 hexadecimal digit of the input address data, for example).
FIG. 2 is a schematic diagram showing an example of a program which is executed by a CPU. Referring to FIG. 2, the program includes instructions (1), (2), . . . to be executed. The main memory preliminarily stores a plurality of instructions in its corresponding addresses. When the program of FIG. 2 is executed by the CPU, the CPU first refers to input address data (which is supplied from a program counter) with regard to the first instruction (1) of the program. The input address data xe2x80x9c00000040xe2x80x9d with regard to the first instruction (1) indicates that the first instruction (1) has preliminarily been stored in an address xe2x80x9c00000040xe2x80x9d of the main memory. With regard to the first instruction (1), the CPU (concretely, the comparator 802 of the direct mapping cache memory shown in FIG. 1) judges whether the tag xe2x80x9c00000xe2x80x9d extracted from the input address data xe2x80x9c00000040xe2x80x9d matches a tag which have been stored in a cache line (of the cache table 801 shown in FIG. 1.) corresponding to the index xe2x80x9c04xe2x80x9d. If matched, data corresponding to the matched tag is read out from the cache table 801 of the direct mapping cache memory and sent to the CPU (instruction decoder). If not matched, the CPU makes access to the main memory and fetches the first instruction (1) from the address xe2x80x9c00000040xe2x80x9d of the main memory. In this case (not matched), the cache line corresponding to the index xe2x80x9c04xe2x80x9d is rewritten, that is, the data of the cache line corresponding to the index xe2x80x9c04xe2x80x9d is changed into the data fetched from the main memory and the tag of the cache line is changed into the tag xe2x80x9c00000xe2x80x9d corresponding to the input address data xe2x80x9c00000040xe2x80x9d. Thereafter, the same processes are executed for the subsequent instructions (2), (3), . . . . By use of the direct mapping cache memory, the number of access of the CPU to the main memory (needing long access time) is reduced, and thereby high speed program execution by the CPU (cache process) is realized.
FIGS. 3A and 3B are schematic diagrams showing examples of change of statuses of the cache table 801 of the direct mapping cache memory of FIG. 1 when the program of FIG. 2 is executed by the CPU, in which FIG. 3A shows the status of the cache table 801 just after the execution of the instruction (1) of FIG. 2 by the CPU and FIG. 3B shows the status of the cache table 801 just after the execution of the instruction (5) of FIG. 2 by the CPU. Referring to FIG. 3A, at the point when the instruction (1) has just been executed, a cache line of the cache table 801 corresponding to an index xe2x80x9c04xe2x80x9d stores a tag xe2x80x9c00000xe2x80x9d (corresponding to the input address data xe2x80x9c00000040xe2x80x9d) and data corresponding to the tag xe2x80x9c00000xe2x80x9d. Referring to FIG. 3B, at the point when the instruction (5) has just been executed, the same cache line of the cache table 801 corresponding to the index xe2x80x9c04xe2x80x9d stores a tag xe2x80x9c00001xe2x80x9d (corresponding to the input address data xe2x80x9c00001040xe2x80x9d) and data corresponding to the tag xe2x80x9c00001xe2x80x9d.
FIGS. 4A and 4B are schematic diagrams showing access time of the CPU employing the direct mapping cache memory when the program of FIG. 2 is executed twice, in which FIG. 4A shows a case where the program of FIG. 2 is executed for the first time and FIG. 4B shows a case where the program of FIG. 2 is executed for the second time. Incidentally, the following explanation concerning program execution time will be given on the assumption that the length of a data storage area of each cache line of the direct mapping cache memory is 4 words (16 bytes) and the length of each instruction of the program of FIG. 2 is 1 word (4 bytes) (that is, on the assumption that 4 instructions are stored in the data storage area of each cache line of the direct mapping cache memory). Access time necessary for fetching data (instruction) from the main memory is assumed to be 100 ns for the first word, and 30 ns for each of the following 3 words. Therefore, access time necessary for fetching data of 4 words (4 instructions) from the main memory and storing the data in a cache line of the direct mapping cache memory becomes 100+30+30+30=190 ns. If we assume the CPU takes 10 ns for reading and executing an instruction which has just been stored in the cache line of the direct mapping cache memory, access time necessary for fetching first 4 words of data (first 4 instructions) from the CPU, storing the data in the direct mapping cache memory and executing the stored first instruction (1) becomes 190+10=200 ns.
In the initialization, all the cache lines of the direct mapping cache memory are set invalid, that is, all the valid bits V of the cache lines are set to xe2x80x9c0xe2x80x9d. Just after the initialization, no data substantially exists in the direct mapping cache memory since the valid bits V are all xe2x80x9c0xe2x80x9d. Therefore, the CPU fetches necessary data (instructions (1) through (4) corresponding to the first index xe2x80x9c04xe2x80x9d of the program of FIG. 2) from the main memory, and writes the fetched instructions (1) through (4) in a cache line of the direct mapping cache memory corresponding to the index xe2x80x9c04xe2x80x9d. By the data writing, the cache line of the direct mapping cache memory corresponding to the index xe2x80x9c04xe2x80x9d is turned valid, that is, the valid bit V of the cache line is set to xe2x80x9c1xe2x80x9d (see FIG. 1). Thereafter, the CPU reads the first instruction (1) from the cache line of the direct mapping cache memory and executes the instruction (1). In the first program execution shown in FIG. 4A, it takes 100+30+30+30+10=200 ns for the CPU to execute the first instruction (1) after a start up routine. Each of the following instructions (2), (3) and (4) takes 10 ns to be executed, respectively (30 ns). Thereafter, the following four instructions corresponding to addresses 00001030 through 0000103C are executed by the CPU in the same way (200+10+10+10=230 ns).
When the instruction (5) shown in FIG. 2 (corresponding to the aforementioned index xe2x80x9c04xe2x80x9d) is to be executed by the CPU, the instruction (1) and the tag (00000) corresponding to the instruction (1) have already been stored in the cache line of the direct mapping cache memory corresponding to the index xe2x80x9c04xe2x80x9d. Therefore, a miss hit (00001xe2x89xa000000) occurs in the cache line of the direct mapping cache memory corresponding to the index xe2x80x9c04xe2x80x9d. Therefore, the CPU fetches the instruction (5) from the main memory and stores the instruction (5) and a corresponding tag (00001) in the cache line corresponding to the index xe2x80x9c04xe2x80x9d. Due to the miss hit, the execution of the instruction (5) also takes 100+30+30+30+10=200 ns. Each of the following three instructions takes 10 ns to be executed, respectively. Therefore, total program execution time in the first program execution becomes 230xc3x973=690 ns.
At the point when the first program execution shown in FIG. 4A is finished, the cache line corresponding to the index xe2x80x9c04xe2x80x9d stores the tag xe2x80x9c00001xe2x80x9d corresponding to the instruction (5) as shown in FIG. 3B. Therefore, when the instruction (1) (corresponding to the aforementioned index xe2x80x9c04xe2x80x9d) is to be executed by the CPU in the second program execution, a miss hit (00000xe2x89xa000001) occurs again to the cache line corresponding to the index xe2x80x9c04xe2x80x9d, thereby the CPU fetches the instruction (1) from the main memory again, and thus the instruction (1) in the second program execution takes 200 ns to be executed. Each of the following instructions (2), (3) and (4) takes 10 ns to be executed, respectively (30 ns). Thereafter, the following four instructions corresponding to addresses 00001030 through 0000103C are executed by the CPU using cache data which have already been stored in a cache line of the direct mapping cache memory corresponding to the index xe2x80x9c03xe2x80x9d (10+10+10+10=40 ns). Thereafter, when the instruction (5) (corresponding to the aforementioned index xe2x80x9c04xe2x80x9d) is to be executed by the CPU in the second program execution, a miss hit (00001xe2x89xa000000) occurs again to the cache line corresponding to the index xe2x80x9c04xe2x80x9d in similar manner (200 ns). Each of the following three instructions takes 10 ns to be executed, respectively (30 ns). Therefore, total program execution time in the second program execution becomes 230+40+230=500 ns. Therefore, total execution time for executing the program of FIG. 2 twice becomes 690+500=1190 ns.
As shown above, cache misses (miss hits) occur easily and frequently in the direct mapping cache memory though the direct mapping cache memory can implement high speed access with a small circuit scale. The access to the main memory due to the cache miss takes as long as 200 ns for example, and thus the program execution time of the CPU (the access time of the CPU for executing a program) is necessitated to be long.
In order to improve the cache hit rate and reduce the memory access time and the program execution time, hierarchical cache memory composed of a primary cache memory and a secondary cache memory is widely used. In a xe2x80x9ccache memory control methodxe2x80x9d disclosed in Japanese Patent Application Laid-Open No.SHO61-241853 for example, a primary cache memory is provided between the CPU and the main memory, and a secondary cache memory is provided between the primary cache memory and the main memory. In the case where a cache hit occurred to the primary cache memory, necessary data which has been stored in the primary cache memory is supplied to the CPU as cache data. In the case where a miss hit occurred to the primary cache memory and a cache hit occurred to the secondary cache memory, necessary data which has been stored in the secondary cache memory is transferred to the primary cache memory, and the necessary data is supplied to the CPU. In this case, if there is no invalid (unused) cache line (to which the necessary data from the secondary cache memory can be transferred) in the primary cache memory, data which has been stored in a cache line of the primary cache memory is eliminated from the primary cache memory and transferred to a cache line of the secondary cache memory. In this case, if there is no invalid (unused) cache line (in which the data eliminated from the primary cache memory can be stored) in the secondary cache memory, data which has been stored in a cache line of the secondary cache memory is eliminated from the secondary cache memory (deleted) so that the data eliminated from the primary cache memory can be stored in the cache line of the secondary cache memory. In the case where miss hits occurred to both the primary cache memory and the secondary cache memory, the necessary data is fetched from the main memory and is written into the primary cache memory (The fetched data is not written into the secondary cache memory.), while the fetched data is generally written into both the primary cache memory and the secondary cache memory in ordinary hierarchical cache memory. By such operations, the cache hit rate of the secondary cache memory is improved.
In a conventional xe2x80x9chierarchical cache systemxe2x80x9d which has been disclosed in Japanese Patent Application Laid-Open No.HEI5-73415, the CPU judges whether or not necessary data exists in the primary cache memory or in the secondary cache memory. When the necessary data is not found in the primary cache memory and found in the secondary cache memory, the data found in the secondary cache memory is transferred to the primary cache memory. In this process, data which is eliminated from the primary cache memory is transferred to the secondary cache memory.
A conventional xe2x80x9ccache memory systemxe2x80x9d which has been disclosed in Japanese Patent Application Laid-Open No.HEI6-012323 employs direct mapping cache memory for the primary cache memory and full-set associative cache memory for the secondary cache memory. The tag comparison for the judgment on the cache hit is executed simultaneously in the primary cache memory and the secondary cache memory. Data which is fetched from the main memory is written into both the primary cache memory and the secondary cache memory according to conventional techniques of the hierarchical cache memory. In the document, a counter for counting the number of access to each cache line of the secondary cache memory (the full-set associative cache memory) is proposed. When the counter of a cache line exceeded a preset value, the cache line is loaded onto the primary cache memory (the direct mapping cache memory) for subsequent access.
In a conventional xe2x80x9cdata processing system employing hierarchical cache memoryxe2x80x9d which has been disclosed in Japanese Patent Application Laid-Open No.HEI6-250926, when a miss hit (cache miss) occurred to the primary cache memory, the secondary cache memory is made access to. If a cache hit occurred to the secondary cache memory, the necessary data stored in the secondary cache memory is transferred to the primary cache memory (invalidated in the secondary cache memory) and supplied to the CPU. If a miss hit occurred also to the secondary cache memory, the main memory is made access to and necessary data is fetched from the main memory. In an embodiment of the document, data fetched from the main memory is transferred and registered in the primary cache memory only (not registered in the secondary cache memory) if the primary cache memory has enough memory space. If the primary cache memory does not have enough memory space, the data fetched from the main memory is registered in the secondary cache memory only (not registered in the primary cache memory). In another embodiment of the document, the data fetched from the main memory is directly registered in the primary cache memory only (not registered in the secondary cache memory). If data that can not be registered in the primary cache memory occurred in the direct data registration from the main memory to the primary cache memory, the data is transferred from the primary cache memory and registered in the secondary cache memory.
As described above, in the conventional direct mapping cache memory, preservation of high-hit-rate cache lines is impossible. The direct mapping cache memory can store only one cache line with respect to a particular index, and thus miss hits occur frequently and repeatedly and thereby the number of access to the main memory is necessitated to be large.
The cache hit rate could be improved by employing the hierarchical cache memory including the primary cache memory and the secondary cache memory. However, access to the secondary cache memory generally takes extra access time and thereby program execution time of the data processing unit such as the CPU is necessitated to be longer. There has been a conventional hierarchical cache memory which executes the tag comparison simultaneously in the primary cache memory (direct mapping cache memory) and the secondary cache memory (full-set associative cash memory). However, there remains plenty of room for improvement in the preservation of high-hit-rate cache lines in the full-set associative cash memory. Further, there are cases where particular data (the same data) is stored both in the direct mapping cache memory and in the full-set associative cash memory, thereby the usage efficiency of memory space of the cache memory is deteriorated and the amount of cache data which can be stored in the cache memory is reduced, and thus the cache hit rate can not be increased to the maximum.
It is therefore the primary object of the present invention to provide a cache system and a cache processing method, by which both high speed data access and a high cache hit rate are realized in high levels by coupling full-set associative cash memory and non-full-set associative cash memory together, and by improving the capability of preserving high-hit-rate cache lines of the cache system and by raising the usage efficiency of memory space of the cache system, and thereby the number of access of the data processing unit such as a CPU, an MPU, etc. to external memory such as main memory and data access time of the data processing unit can be reduced to minimum.
In accordance with a first aspect of the present invention, there is provided a cache system for decreasing the number of access of a data processing unit such as a CPU (Central Processing Unit), an MPU (MicroProcessor Unit), etc. to external memory such as main memory, comprising full-set associative cash memory, non-full-set associative cash memory, cache hit count storage means and a cache hit count management means. The full-set associative cash memory is memory capable of preserving cache lines of high cache hit rates. When a first tag extracted from input address data matched one of first tags which have been stored in valid cache lines of the full-set associative cash memory, data which has been stored in a valid cache line corresponding to the matched first tag is read by the data processing unit as cache data. The non-full-set associative cash memory is provided to the cache system so as to be coupled with the full-set associative cash memory and to execute tag comparison for the judgment on the cache hit simultaneously with the full-set associative cash memory. When a second tag extracted from the input address data matched a second tag which has been stored in a valid cache line of the non-full-set associative cash memory corresponding to an index extracted from the input address data, data which has been stored in the valid cache line corresponding to the matched second tag is read by the data processing unit as cache data. Each of the cache hit count storage means is provided corresponding to each of the cache lines of the full-set associative cash memory for storing a cache hit count value concerning the number of cache hits which occurred to the cache line. The cache hit count management means counts the number of cache hits in each cache line of the full-set associative cash memory and thereby manages and updates the cache hit count values which are stored in the cache hit count storage means. If miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has no invalid cache line corresponding to the index and the full-set associative cash memory has one or more invalid cache lines, data which has been stored in a valid cache line of the non-full-set associative cash memory corresponding to the index to which the miss hit occurred is transferred to one of the invalid cache lines of the full-set associative cash memory, and data fetched from the external memory due to the miss hits is written into the cache line of the non-full-set associative cash memory from which data has been transferred to the full-set associative cash memory. If miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has no invalid cache line corresponding to the index and the full-set associative cash memory is full of valid cache lines, data which has been stored in a valid cache line of the non-full-set associative cash memory corresponding to the index to which the miss hit occurred is transferred to one of valid cache lines of the full-set associative cash memory having the smallest cache hit count value, and data fetched from the external memory due to the miss hits is written into the cache line of the non-full-set associative cash memory from which data has been transferred to the full-set associative cash memory. If miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has an invalid cache line corresponding to the index, data fetched from the external memory due to the miss hits is written into an invalid cache line of the non-full-set associative cash memory corresponding to the index.
In accordance with a second aspect of the present invention, in the first aspect, when a cache hit occurred to a cache line of the full-set associative cash memory, the cache hit count management means increments the cache hit count value of the cache line by 1, and when miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory, the cache hit count management means decrements the cache hit count values of all the cache lines of the full-set associative cash memory by 1 at once.
In accordance with a third aspect of the present invention, in the first aspect, when a cache hit occurred to a cache line of the full-set associative cash memory, the cache hit count management means increments the cache hit count value of the cache line by 1, and when a miss hit occurred to the full-set associative cash memory, the cache hit count management means decrements the cache hit count values of all the cache lines of the full-set associative cash memory by 1 at once.
In accordance with a fourth aspect of the present invention, in the first aspect, when a cache hit occurred to a cache line of the full-set associative cash memory, the cache hit count management means increments the cache hit count value of the cache line by 1.
In accordance with a fifth aspect of the present invention, in the first aspect, the cache system further comprises cache hit date/time storage means. Each of the cache hit date/time storage means is provided corresponding to each of the cache lines of the full-set associative cash memory for storing data concerning the date and time of a recent cache hit which occurred to the cache line. In the case where miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has no invalid cache line corresponding to the index and the full-set associative cash memory is full of valid cache lines, a least recently used cache line is selected from the valid cache lines of the full-set associative cash memory having the smallest cache hit count value based on the data stored in the cache hit date/time storage means, and the selected least recently used cache line is designated as the destination of the data transfer from the non-full-set associative cash memory to the full-set associative cash memory.
In accordance with a sixth aspect of the present invention, in the first aspect, direct mapping cache memory is employed as the non-full-set associative cash memory.
In accordance with a seventh aspect of the present invention, in the first aspect, N-way set associative cache memory (N=2, 4, 8, . . . ) is employed as the non-full-set associative cash memory.
In accordance with an eighth aspect of the present invention, in the seventh aspect, the cache system further comprises LRU storage means. Each of the LRU storage means is provided corresponding to each index for storing an LRU (least recently used) value for indicating a least recently used one of the N cache lines corresponding to the index. In the case where miss hits occurred to both the full-set associative cash memory and the N-way set associative cache memory when the N-way set associative cache memory has no invalid cache line corresponding to the index and the full-set associative cash memory has one or more invalid cache lines, a cache line designated by the LRU value is selected from the N miss hit cache lines of the N-way set associative cache table and data which has been stored in the selected cache line is transferred to one of invalid cache lines of the full-set associative cash memory, and data fetched from the external memory due to the miss hits is written into the selected cache line of the N-way set associative cache table from which data has been transferred to the full-set associative cash memory. In the case where miss hits occurred to both the full-set associative cash memory and the N-way set associative cache memory when the N-way set associative cache memory has no invalid cache line corresponding to the index and the full-set associative cash memory is full of valid cache lines, a cache line designated by the LRU value is selected from the N miss hit cache lines of the N-way set associative cache table and data which has been stored in the selected cache line is transferred to one of valid cache lines of the full-set associative cash memory having the smallest cache hit count value, and data fetched from the external memory due to the miss hits is written into the selected cache line of the N-way set associative cache table from which data has been transferred to the full-set associative cash memory. In the case where miss hits occurred to both the full-set associative cash memory and the N-way set associative cache memory when the N-way set associative cache memory has one or more invalid cache lines corresponding to the index, data fetched from the external memory due to the miss hits is written into one of the invalid cache lines of the N-way set associative cache memory corresponding to the index.
In accordance with a ninth aspect of the present invention, in the eighth aspect, the cache system further comprises cache hit date/time storage means. Each of the cache hit date/time storage means is provided corresponding to each of the cache lines of the full-set associative cash memory for storing data concerning the date and time of a recent cache hit which occurred to the cache line. In the case where miss hits occurred to both the full-set associative cash memory and the N-way set associative cache memory when the N-way set associative cache memory has no invalid cache line corresponding to the index and the full-set associative cash memory is full of valid cache lines, a least recently used cache line is selected from the valid cache lines of the full-set associative cash memory having the smallest cache hit count value based on the data stored in the cache hit date/time storage means, and the selected least recently used cache line is designated as the destination of the data transfer from the N-way set associative cache memory to the full-set associative cash memory.
In accordance with a tenth aspect of the present invention, in the first aspect, the cache system further comprises secondary cache memory which is provided in addition to primary cache memory composed of the full-set associative cash memory and the non-full-set associative cash memory.
In accordance with an eleventh aspect of the present invention, there is provided a cache processing method for decreasing the number of access of a data processing unit such as a CPU (Central Processing Unit), an MPU (MicroProcessor Unit), etc. to external memory such as main memory, employing a combination of full-set associative cash memory capable of preserving high-hit-rate cache lines and non-full-set associative cash memory which executes tag comparison for the judgment on the cache hit simultaneously with the full-set associative cash memory. The cache processing method comprises a first tag comparison step, a second tag comparison step, a cache hit count management step, a first cache data reading process, a second cache data reading process, a first data transfer step, a second data transfer step and a third data transfer step. In the first tag comparison step, a first tag extracted from input address data is compared with first tags which have been stored in valid cache lines of the full-set associative cash memory and it is judged that a cache hit occurred to the full-set associative cash memory if the extracted first tag matched one of the stored first tags. The second tag comparison step is executed simultaneously with the first tag comparison step. In the second tag comparison step, a second tag extracted from the input address data is compared with one or more second tags which have been stored in one or more valid cache lines of the non-full-set associative cash memory corresponding to an index extracted from the input address data and it is judged that a cache hit occurred to the non-full-set associative cash memory if the extracted second tag matched one of the stored second tags corresponding to the index. In the cache hit count management step, the number of cache hits which occurred to each cache line of the full-set associative cash memory is counted and thereby cache hit count values with respect to the cache lines of the full-set associative cash memory which are stored in cache hit count storage means corresponding to the cache lines are updated. In the first cache data reading process, if a cache hit occurred to the full-set associative cash memory in the first tag comparison step, data which has been stored in a valid cache line of the full-set associative cash memory corresponding to the matched first tag is read by the data processing unit as cache data. In the second cache data reading process, if a cache hit occurred to the non-full-set associative cash memory in the second tag comparison step, data which has been stored in a valid cache line of the non-full-set associative cash memory corresponding to the index and the matched second tag is read by the data processing unit as cache data. In the first data transfer step, if miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has no invalid cache line corresponding to the index and the full-set associative cash memory has one or more invalid cache lines, data which has been stored in a valid cache line of the non-full-set associative cash memory corresponding to the index to which the miss hit occurred is transferred to one of the invalid cache lines of the full-set associative cash memory, and data fetched from the external memory due to the miss hits is written into the cache line of the non-full-set associative cash memory from which data has been transferred to the full-set associative cash memory. In the second data transfer step, if miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has no invalid cache line corresponding to the index and the full-set associative cash memory is full of valid cache lines, the data which has been stored in a valid cache line of the non-full-set associative cash memory corresponding to the index to which the miss hit occurred is transferred to one of valid cache lines of the full-set associative cash memory having the smallest cache hit count value, and data fetched from the external memory due to the miss hits is written into the cache line of the non-full-set associative cash memory from which data has been transferred to the full-set associative cash memory. In the third data transfer step, if miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory when the non-full-set associative cash memory has an invalid cache line corresponding to the index, data fetched from the external memory due to the miss hits is written into an invalid cache line of the non-full-set associative cash memory corresponding to the index.
In accordance with a twelfth aspect of the present invention, in the cache hit count management step of the eleventh aspect, when a cache hit occurred to a cache line of the full-set associative cash memory, the cache hit count value of the cache line is incremented by 1, and when miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory, the cache hit count values of all the cache lines of the full-set associative cash memory are decremented by 1 at once.
In accordance with a thirteenth aspect of the present invention, in the cache hit count management step of the eleventh aspect, when a cache hit occurred to a cache line of the full-set associative cash memory, the cache hit count value of the cache line is incremented by 1, and when a miss hit occurred to the full-set associative cash memory, the cache hit count values of all the cache lines of the full-set associative cash memory are decremented by 1 at once.
In accordance with a fourteenth aspect of the present invention, in the cache hit count management step of the eleventh aspect, when a cache hit occurred to a cache line of the full-set associative cash memory, the cache hit count value of the cache line is incremented by 1.
In accordance with a fifteenth aspect of the present invention, in the eleventh aspect, the cache processing method further comprises a cache hit date/time storage step. In the cache hit date/time storage step, data concerning the date and time of a recent cache hit which occurred to a cache line of the full-set associative cash memory is stored in a cache hit date/time storage means which is provided corresponding to the cache line. In the second data transfer step, a least recently used cache line is selected from the valid cache lines of the full-set associative cash memory having the smallest cache hit count value based on the data stored in the cache hit date/time storage means, and the selected least recently used cache line is designated as the destination of the data transfer from the non-full-set associative cash memory to the full-set associative cash memory.
In accordance with a sixteenth aspect of the present invention, in the eleventh aspect, direct mapping cache memory is employed as the non-full-set associative cash memory.
In accordance with a seventeenth aspect of the present invention, in the eleventh aspect, N-way set associative cache memory (N=2, 4, 8, . . . ) is employed as the non-full-set associative cash memory.
In accordance with an eighteenth aspect of the present invention, in the seventeenth aspect, the cache processing method further comprises an LRU storage step. In the LRU storage step, an LRU (least recently used) value for indicating a least recently used one of the N cache lines of the N-way set associative cache memory corresponding to an index is stored in an LRU storage means which is provided corresponding to the index. In the first data transfer step, a cache line designated by the LRU value is selected from the N miss hit cache lines of the N-way set associative cache table and data which has been stored in the selected cache line is transferred to one of invalid cache lines of the full-set associative cash memory, and data fetched from the external memory due to the miss hits is written into the selected cache line of the N-way set associative cache table from which data has been transferred to the full-set associative cash memory. In the second data transfer step, a cache line designated by the LRU value is selected from the N miss hit cache lines of the N-way set associative cache table and data which has been stored in the selected cache line is transferred to one of valid cache lines of the full-set associative cash memory having the smallest cache hit count value, and data fetched from the external memory due to the miss hits is written into the selected cache line of the N-way set associative cache table from which data has been transferred to the full-set associative cash memory. In the third data transfer step, data fetched from the external memory due to the miss hits is written into one of invalid cache lines of the N-way set associative cache memory corresponding to the index.
In accordance with a nineteenth aspect of the present invention, in the eighteenth aspect, the cache processing method further comprises a cache hit date/time storage step. In the cache hit date/time storage step, data concerning the date and time of a recent cache hit which occurred to a cache line of the full-set associative cash memory is stored in a cache hit date/time storage means which is provided corresponding to the cache line. In the second data transfer step, a least recently used cache line is selected from the valid cache lines of the full-set associative cash memory having the smallest cache hit count value based on the data stored in the cache hit date/time storage means, and the selected least recently used cache line is designated as the destination of the data transfer from the N-way set associative cache table to the full-set associative cash memory.
In accordance with a twentieth aspect of the present invention, in the eleventh aspect, the cache processing method further comprises a secondary cache access step in which secondary cache memory, which is provided in addition to primary cache memory composed of the full-set associative cash memory and the non-full-set associative cash memory, is made access to in the case where miss hits occurred to both the full-set associative cash memory and the non-full-set associative cash memory.
In accordance with twenty-first through thirtieth aspects of the present invention, there are provided computer-readable record mediums storing programs for instructing a computer to execute essential parts of the cache processing methods of the eleventh through twentieth aspects of the present invention.